// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-11 19:54
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DynamicPlan;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.stream.IntStream;

public class MinCostClimbingStairs {
    public int minCostClimbingStairsT(int[] cost) {
        int n = cost.length;
        int prev = 0, curr = 0;
        for (int i = 2; i <= n; i++) {
            int next = Math.min(curr + cost[i - 1], prev + cost[i - 2]);
            prev = curr;
            curr = next;
        }
        return curr;
    }

    /**
     * 爬楼梯的最小数量
     */
    public int minCostClimbingStairs(int[] cost) {
        /*
            1 设定状态位 -> 增加维度避免影响 -> 增加一维cost[i][0] 表示当前不爬这阶的最小消耗，cost[i][1] 表示当前爬这阶的最小消耗
            2 状态转移方程 -> 当前状态直接收到前一个状态的影响 -> 不走当前台阶 + 走当前台阶
            3 初始化 -> dp[0][0] = 0,dp[0][1] = nums[0]
            4 输出-> 状态数组记录的当前最小所需的消耗
            5 空间优化-> 滚动数组
            到达每一步台阶之后可以继续向前走一步或者两步 -> 当前台阶不走前一个台阶肯定走过
            当前台阶走过前一个台阶可能走过也可能没走过前前一个台阶可能走过，也可能没有走过，取最大值
         */
        int n = cost.length;
        int[][] dp = new int[n][2];
        // 初始化
        // 第零个台阶没有踩则起点是第一个台阶
        dp[0][0] = cost[0];
        // 第一个台阶没有踩则起点是第0个台阶
        dp[1][0] = cost[0];
        dp[1][1] = cost[1];
        dp[0][1] = cost[0];
        for (int i = 2; i < n; i++) {
            dp[i][0] = dp[i - 1][1];
            dp[i][1] = Math.min(dp[i - 2][1], Math.min(dp[i - 1][0], dp[i - 1][1])) + cost[i];
        }
        return Math.min(dp[n - 1][0], dp[n - 1][1]);
    }


    @Test
    public void shout() {
//        int[] test = {10, 15, 20};
        int[] test = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
        System.out.println(minCostClimbingStairs(test));
    }
}
